package data_structure.homework;

import data_structure.mooc.LinkedList;

public class LinkedList2<E> {

    private class Node {
        public E e;
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this (e, null);
        }

        public Node() {
            this (null, null);
        }

        public Node parseArr(E []arr){
            Node node=new Node (arr[0]);
            Node head=node;
            for(int i = 1; i < arr.length; i++){
                node.next=new Node (arr[i]);
                node=node.next;
            }
            return head;
        }

        @Override
        public String toString() {
            return e.toString ();
        }
    }
    private Node dummyHead;
    private int size;
    public LinkedList2(){
        dummyHead=new Node(null,null);
        size=0;
    }
    public boolean isEmpty(){
        return size==0;
    }
    public int getSize(){
        return size;
    }
    //addition
    public void add(E e,int index){
        if(dummyHead.next==null){
            dummyHead.next=new Node(e);
        }else{
            add(dummyHead,e,index,0);
        }
        size++;
    }
    public void addFirst(E e){
        add(e,0);
    }
    private void add(Node head,E e,int index,int depth){
        if(index<0||index>=size){
            throw new IllegalArgumentException ("Add failed,Illegal index.");
        }
        if(index==depth){
            Node temp=head.next;
            Node node=new Node(e);
            head.next=node;
            node.next=temp;
        }else{
            depth++;
            head=head.next;
            add(head,e,index,depth);
        }

    }
    public void addLast(E e){
        add (e,size-1);
    }
    //deletion

    public E remove(int index){
        if(index<0||index>=size){
            throw new IllegalArgumentException ("Remove failed,Illegal index.");
        }
        size--;
        return remove(dummyHead,index,0);
    }
    private E remove(Node head,int index,int flag){
        if(index==flag){
            Node prev=head;
            Node del=head.next;
            prev.next=del.next;
            del.next=null;
            return del.e;
        }else{
            head=head.next;
            flag++;
        }
        return remove(head, index, flag);
    }
    public E removeFirst(){
        return remove (0);
    }
    public E removeLast(){
        return remove (size-1);
    }
    //look-up

    public E get(int index){
        if(index<0||index>=size){
            throw new IllegalArgumentException ("Get failed,Illegal index.");
        }
        return get(dummyHead,index,0);
    }
    private E get(Node head,int index,int flag){

        if(index==flag){
            Node node=head.next;
            return node.e;
        }else{
            flag++;
            head=head.next;
        }
        return get (head, index, flag);
    }

    public E getFirst(){
        return get(0);
    }
    public E getLast(){
        return get(size-1);
    }
    //modification
    public E set(int index,E e){
        if(index<0||index>=size){
            throw new IllegalArgumentException ("Set failed,Illegal index.");
        }
        return set(dummyHead,index,e,0);
    }
    private E set(Node head,int index,E e,int flag){
        if(flag==index){
            Node target=head.next;
            E res=target.e;
            target.e=e;
            return res;
        }else{
            head=head.next;
            flag++;
        }
        return set (head, index, e, flag);
    }
    public E setFirst(E e){
        return set(0,e);
    }
    public E setLast(E e){
        return set(size-1,e);
    }
    public String toString() {
        StringBuilder sb = new StringBuilder("List:");
        Node current = dummyHead.next;
        while (current != null) {
            sb.append (current.e).append ("-->");
            current=current.next;
        }
        sb.append("NULL");
        return sb.toString ();
    }

    public static void main(String[] args) {
        LinkedList2<Integer>list = new LinkedList2<> ();
        for(int i=0;i<5;i++){
            list.addFirst (i);
            System.out.println(list.toString ());
        }
        list.add (100000,4);
        System.out.println(list.toString ());
        System.out.println(list.set (4,-100000));
        System.out.println(list.toString ());

    }
}
